// https://blog.csdn.net/weixin_42449534/article/details/96855834

// https://my.oschina.net/u/4010368/blog/4599489
// 4.快速排序???
function quickSort(arr, left, right) {
    var len = arr.length;
    var partitionIndex;
    var left = typeof left != "number";
    var right = typeof right != "number";
    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
}

function partition(arr, left, right) {
    var pivot = left,
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}